package com.beikai.demo01.sort.impl;

import com.alibaba.fastjson.JSONObject;
import com.beikai.demo01.sort.ArrSort;

/**
 * Created with IntelliJ IDEA.
 *
 * @author : hanbeikai
 * Date: 2021/6/4 10:30 下午
 * Description: 堆排序 主要是利用最大堆和最小堆的特性,父节点总是大于或小于子节点,当通过递归的方式每层进行调整,最后得到最大堆或最小堆,则完成排序
 * 堆的底层是数组,另外,有两个公式要注意
 * 加入当前对元素的节点是i,则其左节点是 2*i+1,右节点是 2*i+2
 * 例如,堆顶是0 ,则其左节点的坐标是1 右节点是2
 * <p>
 * 堆节点的排序主要分两步,
 * 第一步 ,先构建最大堆
 * 第二步 ,把堆顶与最后一个元素交换,然后不断的调整直到最后
 *
 * handle()
 * 排序之前的数组: [9,8,7,6,5,10,3,2,1,1]
 * [10,8,9,6,5,7,3,2,1,1]
 * 排序之后的数组: [1,1,2,3,5,6,7,8,9,10]
 * 96
 *
 * handle2()
 * 排序之前的数组: [9,8,7,6,5,10,3,2,1,1]
 * [10,8,9,6,5,7,3,2,1,1]
 * 排序之后的数组: [1,1,2,3,5,6,7,8,9,10]
 * 1
 */
public class HeapSort extends ArrSort {


    @Override
    public int[] sort(int[] arr) {

        // 获取数组的长度,遍历层级
        buildMaxHeap(arr);

        System.out.println(JSONObject.toJSONString(arr));

        // 重新调整
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr,0,i);
            handle(arr,0,i);
        }

        return arr;
    }

    /**
     * 构建最大堆
     *
     * @param arr
     */
    private void buildMaxHeap(int[] arr) {
        if (arr.length < 2){
            return;
        }
        // 计算最后一个有子节点的父节点坐标, 根据 子左节点坐标 = 2*父节点+1 子右节点 = 2*父节点+2 可到到父节点 = (子右节点 -2) / 2
        for (int i = (arr.length - 2)  >> 1; i >= 0; i--) {
            // 从最后的一层往上遍历 开始处理 比较节点的子节点是不是小于父节点,并且左侧节点小于右侧节点
            handle(arr, i, arr.length);
        }
    }

    /**
     * 堆排序 方式2
     * @param arr
     * @param parentIdx
     * @param length
     */
    private void handle2(int[] arr, int parentIdx, int length){
        int left = getLeft(parentIdx);
        if (left < length){
            int right = getRight(parentIdx);
            handle2(arr,left,length);
            handle2(arr,right,length);
            if (right < length){
                if (arr[right] > arr[left]) {
                    if (arr[right] > arr[parentIdx]){
                        swap(arr,right,parentIdx);
                    }
                }else {
                    if (arr[left] > arr[parentIdx]){
                        swap(arr,left,parentIdx);
                    }
                }
            }else {
                if (arr[left] > arr[parentIdx]){
                    swap(arr,left,parentIdx);
                }
            }
        }
    }

    /**
     * 处理堆节点
     *
     * @param arr
     * @param parentIdx
     * @param length
     */
    private void handle(int[] arr, int parentIdx, int length) {
        // 首先计算左节点
        int left = getLeft(parentIdx);
        // 获取父节点的值
        int tempParent = arr[parentIdx];

        // 遍历构建节点 父节点最大 左侧节点小于右侧节点
        while (left < length){
            // 判断是否有右节点
            if (left + 1 < length) {
                // 判断如果右节点大于左节点,则当前最大节点指向右节点
                if (arr[left] < arr[left + 1]){
                    left++;
                }
            }
            // 判断当前子节点中的最大值是否小于父节点 如果是则跳出循环
            if (tempParent >= arr[left]){
                break;
            }
            // 如果不是,则说明左节点是大的
            arr[parentIdx] = arr[left];
            parentIdx = left;
            // 重新计算子节点
            left = getLeft(left);
        }
        arr[parentIdx] = tempParent;
    }

    /**
     * 获取左节点
     *
     * @param i
     * @return
     */
    private int getLeft(int i) {
        return (i << 1)  + 1;
    }

    /**
     * 获取右节点
     * @param i
     * @return
     */
    private int getRight(int i) {
        return (i << 1) + 2;
    }
}
